home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / rfc / rfc721 < prev    next >
Encoding:
Text File  |  1991-04-20  |  13.2 KB  |  413 lines
  1.  
  2. NWG/RFC 721                                           1 SEP 76 LLG 36636
  3. Out-of-Band Control Signals
  4.  
  5.  
  6.  
  7. Network Working Group                                      Larry Garlick
  8. Request for Comments 721                                         SRI-ARC
  9. NIC 36636                                                 1 September 76
  10.  
  11.                        Out-of-Band Control Signals
  12.                                   in a
  13.                          Host-to-Host Protocol
  14.  
  15. This note addresses the problem of implementing a reliable out-of-band
  16. signal for use in a host-to-host protocol.  It is motivated by the fact
  17. that such a satisfactory mechanism does not exist in the Transmission
  18. Control Protocol (TCP) of Cerf et. al. [reference 4, 6]  In addition to
  19. discussing some requirements for such an out-of-band signal (interrupts)
  20. and the implications for the implementation of the requirements, a
  21. discussion of the problem for the TCP case will be presented.
  22.  
  23. While the ARPANET host-to-host protocol does not support reliable
  24. transmission of either data or controls, it does meet the other
  25. requirements we have for an out-of-band control signal and will be drawn
  26. upon to provide a solution for the TCP case.
  27.  
  28. The TCP currently handles all data and controls on the same logical
  29. channel.  To achieve reliable transmission, it provides positive
  30. acknowledgement and retransmission of all data and most controls.  Since
  31. interrupts are on the same channel as data, the TCP must flush data
  32. whenever an interrupt is sent so as not to be subject to flow control.
  33.  
  34. Functional Requirements
  35.  
  36.    It is desirable to insure reliable delivery of an interrupt.  The
  37.    sender must be assured that one and only one interrupt is delivered
  38.    at the destination for each interrupt it sends.  The protocol need
  39.    not be concerned about the order of delivery of interrupts to the
  40.    user.
  41.  
  42.    The interrupt signal must be independent of data flow control
  43.    mechanisms.  An interrupt must be delivered whether or not there are
  44.    buffers provided for data, whether or not other controls are being
  45.    handled.  The interrupt should not interfere with the reliable
  46.    delivery of other data and controls.
  47.  
  48.    The host-to-host protocol need not provide synchronization between
  49.    the interrupt channel and the data-control channel.  In fact, if
  50.    coupling of the channels relies on the advancement of sequence
  51.    numbers on the data-control channel, then the interrupt channel is no
  52.    longer independent of flow control as required above.  The
  53.    synchronization with the data stream can be performed by the user by
  54.  
  55.  
  56.  
  57.  
  58.  
  59.                                    1
  60.  
  61. NWG/RFC 721                                           1 SEP 76 LLG 36636
  62. Out-of-Band Control Signals
  63.  
  64.  
  65.  
  66.    marking the data stream when an interrupt is generated.  The
  67.    interrupt need not be coupled with other controls since it in no way
  68.    affects the state of a connection.
  69.  
  70.    Once the interrupt has been delivered to the user, no other semantics
  71.    are associated with it at the host-to-host level.
  72.  
  73. Implications
  74.  
  75.    To provide for reliable delivery and accountability of interrupt
  76.    delivery, an acknowledgement scheme is required.  To associate
  77.    interrupt acknowledgements with the correct interrupt, some naming
  78.    convention for interrupts is necessary.  Sequence numbers provide
  79.    such a naming convention, along with the potential for providing an
  80.    ordering mechanism.
  81.  
  82.    A separate interrupt channel is required to make interrupts
  83.    independent of flow control.  A separate sequence number space for
  84.    naming interrupts is also necessary.  If the sequence numbers are
  85.    from the same sequence number space as some other channel, then
  86.    sending an interrupt can be blocked by the need to resynchronize the
  87.    sequence numbers on that channel.
  88.  
  89.    In the current TCP, which uses one channel for data, controls, and
  90.    interrupts, flushing of data is combined with the interrupt to bypass
  91.    the flow control mechanism.  However, flushing of resynchronization
  92.    controls is not allowed and receipt of these controls is dependent on
  93.    the acknowledgement of all previous data.  The ARPANET protocol,
  94.    while not providing for reliable transmission, does provide for the
  95.    separation of the interrupt-control channel and the data channel.
  96.  
  97. Multiple Channels and Sequence Numbers
  98.  
  99.    If multiple channels are to be used for a connection, then it becomes
  100.    interesting to determine how the sequence numbers of the channels can
  101.    be coupled so that sequence number maintenance can be done
  102.    efficiently.
  103.  
  104.    Assigning sequence numbers to each octet of data and control, as in
  105.    the TCP, allows positive acknowledgement and ordering.  However,
  106.    since packets are retransmitted on timeout, and since multi-path
  107.    packet switch networks can cause a packet to stay around for a long
  108.    time, the presence of duplicate packets and out-of-order packets must
  109.    be accounted for.  A sequence number acceptability test must be
  110.    performed on each packet received to determine if one of the
  111.    following actions should be taken:
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.                                    2
  119.  
  120. NWG/RFC 721                                           1 SEP 76 LLG 36636
  121. Out-of-Band Control Signals
  122.  
  123.  
  124.  
  125.       Acknowledge the packet and pass it on to the user.
  126.  
  127.       Acknowledge the packet, but do not send it to the user, since it
  128.       has already been delivered.
  129.  
  130.       Discard the packet; the sequence number is not believable.
  131.  
  132.    Acceptability on Channel 0
  133.  
  134.       To determine the action to be taken for a packet, acceptability
  135.       ranges are defined.  The following three ranges are mutually
  136.       exclusive and collectively exhaustive of the sequence number space
  137.       (see Figure 1):
  138.  
  139.          Ack-deliver range (ADR)
  140.  
  141.          Ack-only range (AOR)
  142.  
  143.          Discard range (DR)
  144.  
  145.  
  146.  
  147.  
  148.  
  149.                     ACCEPTABILITY RANGES
  150.          
  151.       
  152.           DR       AOR             ADR              DR
  153.       \\=====)[===========)[===================](========\\
  154.               ^           ^^                   ^^
  155.               !           !\                   !\
  156.               !           ! FCLE               ! DRLE
  157.             AOLE       AORE                 ADRE
  158.       
  159.       
  160.                           Figure 1
  161.  
  162.  
  163.  
  164.  
  165.       Let  S = size of sequence number space (number per octet)
  166.  
  167.          x = sequence number to be tested
  168.  
  169.          FCLE = flow control left window edge
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.                                    3
  178.  
  179. NWG/RFC 721                                           1 SEP 76 LLG 36636
  180. Out-of-Band Control Signals
  181.  
  182.  
  183.  
  184.          ADRE = (FCLE+ADR) mod S = Ack-deliver right edge (Discard
  185.                   left edge - 1)
  186.  
  187.          AOLE = (FCLE-AOR) mod S =  Ack-only left edge (Discard
  188.                   right edge + 1)
  189.  
  190.          TSE = time since connection establishment (in sec)
  191.  
  192.          MPL = maximum packet lifetime (in sec)
  193.  
  194.          TB = TCP bandwidth (in octets/sec)
  195.  
  196.       For any sequence number, x, and packet text length, l, if
  197.  
  198.          (AOLE <= x <= ADRE) mod S  and
  199.  
  200.          (AOLE <= x+l-1 <= ADRE) mod S
  201.  
  202.       then the packet should be acknowledged.
  203.  
  204.       If x and l satisfy
  205.  
  206.          (FCLE <= x <= ADRE) mod S  and
  207.  
  208.          (FCLE <= x+l-1 <= ADRE) mod S
  209.  
  210.       then x can also be delivered to the user; however, ordered
  211.       delivery requires that x = FCLE.
  212.  
  213.       A packet is not in a range only if all of it lies outside a range.
  214.       When a packet falls in more than one range, precedence is ADR,
  215.       then AOR, then DR.  When a packet falls in the AOR then an ACK
  216.       should be sent, even if a packet has to be created.  The ACK will
  217.       specify the current left window edge.  This assures acknowledgment
  218.       of all duplicates.
  219.  
  220.       ADRE is exactly the maximum sequence number ever "advertised"
  221.       through the flow control window, plus one.  This allows for
  222.       controls to be accepted even though permission for them may never
  223.       have been explicitly given.  Of course, each time a control with a
  224.       sequence number equal to the ADRE is sent, the ADRE must be
  225.       incremented by one.
  226.  
  227.       AOR is set so that old duplicates (from previous incarnations of
  228.       the connection) can be detected and discarded.  Thus
  229.  
  230.          AOR = Min(TSE, MPL) * TB
  231.  
  232.  
  233.  
  234.  
  235.  
  236.                                    4
  237.  
  238. NWG/RFC 721                                           1 SEP 76 LLG 36636
  239. Out-of-Band Control Signals
  240.  
  241.  
  242.  
  243.    Synchronization and Resynchronization Problems
  244.  
  245.       A special problem arises concerning detection of packets (old
  246.       duplicates) in the network that have sequence numbers assigned by
  247.       old instances of a connection.  To handle this reliably, careful
  248.       selection of the initial sequence number is required [ref. 2, 3]
  249.       as well as periodic checks to determine if resynchronization of
  250.       sequence numbers is necessary.  The overhead of such elaborate
  251.       machinery is expensive and repeating it for each additional
  252.       channel is undesirable.
  253.  
  254.    Acceptability on Channel i
  255.  
  256.       We have concluded that the only savings realizable in the muiltple
  257.       channel case is to use channel zero's initial sequence number and
  258.       resynchronization maintenance mechanism for the additional
  259.       channels.  This can be accomplished by coupling each additional
  260.       channel to channel zero's sequence numbers (CZSN), so that each
  261.       item on channel i carries a pair of sequence numbers, the current
  262.       CZSN and the current channel i's sequence number (CISN).
  263.  
  264.       The acceptablility test of items on channel i is a composite test
  265.       of both sequence numbers.  First the CZSN is checked to see if it
  266.       would be acknowledged if it were an octet received on channel
  267.       zero.  Only if it would have been discarded would the item on
  268.       channel i be discarded.  Having passed the CZSN test, the CISN is
  269.       checked to see if the item is deliverable and acknowledgable with
  270.       respect to the CISN sequence number space.  The CISN test is a
  271.       check for everything but the existence of old duplicates from old
  272.       instances of the connection and is performed like the check for
  273.       channel zero items.
  274.  
  275.       It has been shown that to implement additional channels for a TCP
  276.       connection, two alternatives are available-- (1) provide each
  277.       channel with its own initial sequence number and resynchronization
  278.       maintenance mechanism or (2) provide one initial sequence number
  279.       and resynchronization maintenance mechanism for all channels
  280.       through channel zero's mechanism.  It is hard for us to compare
  281.       the two alternatives, since we have no experience implementing any
  282.       resynchronization maintenance mechanism.
  283.  
  284. TCP Case
  285.  
  286.    To implement a completely reliable separate interrupt channel for TCP
  287.    requires a channel with a full sequence number space.  It is possible
  288.    to compromise here and make the interrupt number space smaller than
  289.    that required to support consumption of numbers at the TCP's
  290.  
  291.  
  292.  
  293.  
  294.  
  295.                                    5
  296.  
  297. NWG/RFC 721                                           1 SEP 76 LLG 36636
  298. Out-of-Band Control Signals
  299.  
  300.  
  301.  
  302.    bandwidth.  What is lost is the total independence of the flow
  303.    control from the data-control channel.  Normally, the data-control
  304.    sequence numbers will change often enough so that wraparound in the
  305.    interrupt number space causes no problems.
  306.  
  307.    Things become slightly messy when many interrupts are generated in
  308.    quick succession.  Even if the interrupt numbers are acknowledged,
  309.    they cannot be reused if they refer to the same data-control sequence
  310.    number, until a full packet lifetime has elapsed.  This can be
  311.    remedied in all but one case by sending a NOP on the data-control
  312.    channel so that the next set of interrupts can refer to a new
  313.    data-control sequence number.  However, if the data-control channel
  314.    is blocked due to flow control and a resynchronizing control (DSN in
  315.    the TCP case) was just sent, a NOP cannot be created until the
  316.    resynchronization is complete and a new starting sequence number is
  317.    chosen.  Thus to send another interrupt, the TCP must wait for a
  318.    packet lifetime or an indication that it can send a NOP on the
  319.    data-control channel.  (In reality, a connection would probably be
  320.    closed long before a packet lifetime elapsed if the sender is not
  321.    accepting data from the receiver. [reference 1])
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.                                    6
  355.  
  356. NWG/RFC 721                                           1 SEP 76 LLG 36636
  357. Out-of-Band Control Signals
  358.  
  359.  
  360.  
  361. REFERENCES
  362.  
  363.    (1)  J. Postel, L. Garlick, R. Rom, "TCP Specification (AUTODIN II),"
  364.         ARC Catalog #35938, July 1976.
  365.  
  366.    (2)  R. Tomlinson, "Selecting Sequence Numbers," INWG Protocol Note
  367.         #2, September 1974.
  368.  
  369.    (3)  Y. Dalal, "More on Selecting Sequence Numbers," INWG Protocol
  370.         Note #4, October 1974.
  371.  
  372.    (4)  V. Cerf, Y. Dalal, C. Sunshine, "Specification of Internet
  373.         Transmission Control Program," INWG General Note #72, December
  374.         1974 (Revised). [Also as RFC 675, NIC Catalog #31505.]
  375.  
  376.    (5)  Cerf, V., "TCP Resynchronization," SU-DSL Technical Note #79,
  377.         January 1976.
  378.  
  379.    (6)  Cerf, V. and R. Kahn, "A Protocol for Packet Network
  380.         Intercommunication," IEEE Transactions on Communication, Vol
  381.         COM-20, No. 5, May 1974.
  382.  
  383.    (7)  C. Sunshine, "Interprocess Communication Protocols for Computer
  384.         Networks," Digital Systems Laboratory Technical Note #105,
  385.         December 1975.
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403.  
  404.  
  405.  
  406.  
  407.  
  408.  
  409.  
  410.  
  411.  
  412.  
  413.                                    7